# uncompyle6 version 3.2.3
# Python bytecode 3.6 (3379)
# Decompiled from: Python 3.6.8 |Anaconda custom (64-bit)| (default, Feb 21 2019, 18:30:04) [MSC v.1916 64 bit (AMD64)]
# Embedded file name: site-packages\sqlalchemy\util\topological.py
"""Topological sorting algorithms."""
from ..exc import CircularDependencyError
from .. import util

__all__ = ["sort", "sort_as_subsets", "find_cycles"]


def sort_as_subsets(tuples, allitems, deterministic_order=False):
    edges = util.defaultdict(set)
    for parent, child in tuples:
        edges[child].add(parent)

    Set = util.OrderedSet if deterministic_order else set
    todo = Set(allitems)
    while todo:
        output = Set()
        for node in todo:
            if todo.isdisjoint(edges[node]):
                output.add(node)

        if not output:
            raise CircularDependencyError(
                "Circular dependency detected.",
                find_cycles(tuples, allitems),
                _gen_edges(edges),
            )
        todo.difference_update(output)
        yield output


def sort(tuples, allitems, deterministic_order=False):
    """sort the given list of items by dependency.
    
    'tuples' is a list of tuples representing a partial ordering.
    'deterministic_order' keeps items within a dependency tier in list order.
    """
    for set_ in sort_as_subsets(tuples, allitems, deterministic_order):
        for s in set_:
            yield s


def find_cycles(tuples, allitems):
    edges = util.defaultdict(set)
    for parent, child in tuples:
        edges[parent].add(child)

    nodes_to_test = set(edges)
    output = set()
    for node in nodes_to_test:
        stack = [node]
        todo = nodes_to_test.difference(stack)
        while stack:
            top = stack[-1]
            for node in edges[top]:
                if node in stack:
                    cyc = stack[stack.index(node) :]
                    todo.difference_update(cyc)
                    output.update(cyc)
                if node in todo:
                    stack.append(node)
                    todo.remove(node)
                    break
            else:
                node = stack.pop()

    return output


def _gen_edges(edges):
    return set([(right, left) for left in edges for right in iter(edges[left])])
